//
// Created by ct on 2021/11/2.
//

#ifndef ALGOANDSTRUCT_DAY2_H
#define ALGOANDSTRUCT_DAY2_H

#include <string>
#include <stack>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using std::stack;
using std::string;
using std::unordered_map;
using std::vector;
using std::max;
using std::priority_queue;
using std::pair;

class Day2 {


public:
    static bool isValid(const string &s) {
        stack<char> m_stack;
        for (auto c: s) {
            switch (c) {
                case '(':
                    m_stack.push(')');
                    continue;
                case '[':
                    m_stack.push(']');
                    continue;
                case '{':
                    m_stack.push('}');
                    continue;
                default:

                    if (m_stack.empty() || c != m_stack.top()) {
                        return false;
                    }
                    m_stack.pop();
            }
        }
        return m_stack.empty();
    }

//    int a(){
//        int x =0;
//        int& b = x;
//        return b;
//    }

    static int fib(int n) {

        unordered_map<int, int> un_map;

        un_map[0] = 0;
        un_map[1] = 1;
        un_map[2] = 1;

        return fib_nr(n, un_map);
    }

    static int longestValidParentheses(const string &s) {
        stack<int> st;
        vector<bool> mark(s.length());
        for (auto &&i : mark) i = false;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                if (st.empty()) mark[i] = 1;
                else st.pop();
            }
        }
        while (!st.empty()) {
            mark[st.top()] = 1;
            st.pop();
        }
        int len = 0, ans = 0;
        for (int i = 0; i < mark.size(); ++i) {
            if (mark[i] == 1) {
                len = 0;
                continue;
            }

            len++;
            ans = max(len, ans);
        }
        return ans;
    }

    static int evalRPN(vector<string> &tokens) {
        stack<int> st;
        for (const string &x : tokens) {

            if (x == "+" || x == "-" || x == "*" || x == "/") {
                int num1 = st.top();
                st.pop();
                int num2 = st.top();
                st.pop();
                if (x == "+") st.push(num2 + num1);
                if (x == "-") st.push(num2 - num1);
                if (x == "*") st.push(num2 * num1);
                if (x == "/") st.push(num2 / num1);
            } else {
                st.push(std::stoi(x));
            }

        }
        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
        return result;
    }
    // https://leetcode-cn.com/problems/sliding-window-maximum/
    /*
     示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    static vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        int n = (int) nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans{q.top().first};

        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }

    /*
     假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

   static int climbStairs(int n) {
        unordered_map<int,int> unorderedMap{
            {0,0},
            {1,1},
            {2,2}
        };
        return climbStairs_her(n,unorderedMap);
    }

    static int climbStairs2(int n) {
        if(n == 1){return 1;}
        if(n == 2){return 2;}
        int a = 1 , b = 2 , tmp ;
        for (int i = 3; i <= n; ++i) {
            tmp = a;
            a = b;
            b = tmp + b;
        }
        return b;
    }
private:

    static int climbStairs_her(int n , unordered_map<int,int> & un_map){
        if (n == 0) {
            return un_map[0];
        } else if (n == 1) {
            return un_map[1];
        } else if (n == 2) {
            return un_map[2];
        } else if (un_map.find(n) == un_map.end()) {
            un_map[n] = climbStairs_her(n - 1, un_map) + climbStairs_her(n - 2, un_map);
            return un_map[n];
        } else {
            return un_map[n];
        }


   }


    static int fib_her(int n, unordered_map<int, int> un_map) {
        if (n == 0) {
            return un_map[0];
        } else if (n == 1) {
            return un_map[1];
        } else if (n == 2) {
            return un_map[2];
        } else if (un_map.find(n) == un_map.end()) {
            un_map[n] = fib_her(n - 1, un_map) + fib_her(n - 2, un_map);
            return un_map[n];
        } else {
            return un_map[n];
        }
    }

    static int fib_nr(int n, unordered_map<int, int> un_map) {
        switch (n) {
            case 0:
                return un_map[0];
            case 1:
                return un_map[1];
            case 2:
                return un_map[2];
            default:
                for (int i = 3; i <= n; ++i) {
                    un_map[i] = un_map[i - 1] + un_map[i - 2];
                }
                return un_map[n];
        }
    }
};


#endif //ALGOANDSTRUCT_DAY2_H
